package dataStructure.LinkedList;

import java.util.Stack;

/**
 * @author lhn
 * @date 2024-04-12 14:52
 */

public class SingleLinkedListDemo {
    public static void main(String[] args) {
//        HeroNode hero1 = new HeroNode(1,"宋江1","及时雨1");
//        HeroNode hero2 = new HeroNode(2,"宋江2","及时雨2");
//        HeroNode hero3 = new HeroNode(3,"宋江3","及时雨3");
//
//        SingleLinkedList singleLinkedList = new SingleLinkedList();
//        singleLinkedList.add(hero1);
//        singleLinkedList.add(hero2);
//        singleLinkedList.add(hero3);
//        singleLinkedList.list();

        HeroNode hero4 = new HeroNode(5,"宋江5","及时雨5");
        HeroNode hero5 = new HeroNode(4,"宋江4","及时雨4");
        HeroNode hero6 = new HeroNode(6,"宋江6","及时雨6");

        SingleLinkedList singleLinkedList1 = new SingleLinkedList();
        singleLinkedList1.addByOrder(hero4);
        singleLinkedList1.addByOrder(hero6);
        singleLinkedList1.addByOrder(hero5);
//        singleLinkedList1.list();

        HeroNode hero7 = new HeroNode(5,"吴用","智多星");
        singleLinkedList1.update(hero7);
//        singleLinkedList1.list();
        singleLinkedList1.delete(4);
//        singleLinkedList1.list();

//        System.out.println(getLength(singleLinkedList1.getHead()));
//        System.out.println(findLatIndexNode(singleLinkedList1.getHead(),1));
//        System.out.println(findLatIndexNode(singleLinkedList1.getHead(),0));
//        System.out.println(findLatIndexNode(singleLinkedList1.getHead(),2));
//        System.out.println(findLatIndexNode(singleLinkedList1.getHead(),3));

//        reverseList(singleLinkedList1.getHead());
        System.out.println("this is reversePrint :");
        reversePrint(singleLinkedList1.getHead());

        System.out.println("This is mergeDouble test :");
        HeroNode heroNode1 = new HeroNode(2,"2","2");
        HeroNode heroNode2 = new HeroNode(5,"5","5");
        HeroNode heroNode3 = new HeroNode(9,"9","9");
        SingleLinkedList list1 = new SingleLinkedList();
        list1.add(heroNode1);
        list1.add(heroNode2);
        list1.add(heroNode3);
        HeroNode heroNode4 = new HeroNode(1,"1","1");
        HeroNode heroNode5 = new HeroNode(3,"3","3");
        HeroNode heroNode6 = new HeroNode(10,"10","10");
        SingleLinkedList list2 = new SingleLinkedList();
        list2.add(heroNode4);
        list2.add(heroNode5);
        list2.add(heroNode6);
        HeroNode mergedHead = mergeDoubleList(
                list1.getHead(),list2.getHead()
        );
//        System.out.println(
//                mergedHead
//        );
        SingleLinkedList list3 = new SingleLinkedList();

        list3.setHead(
                mergedHead
        );
        list3.list();

    }
    /* 
    * 
    * @author lihaonan 
    * @date 2024/4/15 16:37
     * @param head 链表的头节点
     * @return int 有效节点个数
    */
    public static int getLength(HeroNode head) {
        if (head.next == null ) {
            return 0;
        }
        int length = 0;
        HeroNode cur = head.next;
        while (cur != null) {
            length ++;
            cur = cur.next;
        }
        return length;
    }
    public static HeroNode findLatIndexNode(HeroNode head, int index){
        if (head.next == null) {
            return null;
        }
        //获取链表长度
        int size = getLength(head);
        if (index <= 0 || index > size) {
            return null;
        }
        HeroNode cur = head.next;
        for (int i = 0; i < (size - index); i++) {
            cur = cur.next;
        }
        return cur;
    }
    //用栈
    public static void reversePrint(HeroNode head) {
        if (head.next == null) {
            return ;
        }
        //创建一个栈，将各个节点压入栈中
        Stack<HeroNode> stack = new Stack<>();
        HeroNode cur = head.next;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        while (stack.size()>0) {
            System.out.println(stack.pop());
        }
    }
    public static void reverseList(HeroNode head){
        if (head.next == null || head.next.next == null){
            return ;
        }
        HeroNode cur = head.next;
        HeroNode next = null;   //指向当前节点[cur]的下一个节点
        HeroNode reverseHead = new HeroNode(0,"","");
        //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead的最前端
        while (cur != null) {
            next = cur.next;    //先暂时保存当前节点的下一个节点
            cur.next = reverseHead.next;    //cur中next用于存放reverseHead中next值
            reverseHead.next = cur;    //将cur连到reverseHead后的第一个位置
            cur = next; //让cur后移
        }
        //将head.next指向reverseHead.next，实现单链表的反转
        head.next = reverseHead.next;
    }
    public static HeroNode mergeDoubleList(HeroNode head1, HeroNode head2) {
        //TODO 如果其中一个链表为空，则直接返回另一个链表
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }
        HeroNode mergeHead = new HeroNode(0,"","");
        HeroNode cur1 = head1.next;
        HeroNode cur2 = head2.next;
        HeroNode cur = mergeHead;
        while (cur1 != null || cur2 != null) {
            if (cur1 != null && cur2 != null) {
                if (cur1.no <= cur2.no) {
                    cur.next = cur1;
                    cur1 = cur1.next;
                } else {
                    cur.next = cur2;
                    cur2 = cur2.next;
                }
            } else if (cur1 == null && cur2 != null) {
                cur.next = cur2;
                cur2 = cur2.next;
            } else if (cur2 == null && cur1 != null) {
                cur.next = cur1;
                cur1 = cur1.next;
            }
//            cur.next.next = null;
            cur = cur.next;
        }
        return mergeHead;
    }

}
class SingleLinkedList {
    //初始化头节点，头节点不存放数据
    private HeroNode head = new HeroNode(0,"","");
    public void setHead(HeroNode head) {
        this.head = head;
    }
    public HeroNode getHead() {
        return head;
    }
    //添加节点到单向链表
    //1.找到当前链表的最后一个节点
    //2.将最后这个节点的next指向新的节点
    public void add(HeroNode heroNode) {
        //因为head节点不能动，因此我们需要一个辅助遍历temp
        HeroNode temp = head;
        while (true) {
            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        //当退出while循环时，temp就指向了链表的最后
        //将最后这个节点的next指向新的节点
        temp.next = heroNode;
    }
    public void addByOrder(HeroNode heroNode) {
        //因为单链表，temp是位于添加位置的前一个节点
        HeroNode temp = head;
        boolean flag = false;   //flag标志添加的编号是否存在，默认为false
        while (true) {
            if (temp.next == null ){
                //已经到链表的最后
                break;
            }
            if (temp.next.no > heroNode.no) {
                //在temp的d当前位置添加
                break;
            } else if (temp.next.no == heroNode.no) {
                //编号已存在
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            System.out.printf("准备插入的英雄编号 %d 已经存在",heroNode.no);
        } else {
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }
    //修改节点的信息，根据no编号来修改，no编号不能修改
    public void update(HeroNode newHeroNode) {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        HeroNode temp = head.next;
        while(true) {
            if (temp == null) {
                System.out.printf("没有找到编号%d的节点,不能修改\n",newHeroNode.no);
                break;
            }
            if (newHeroNode.no == temp.no) {
                temp.name = newHeroNode.name;
                temp.nickname = newHeroNode.nickname;
                System.out.println("修改成功");
                break;
            }
            temp = temp.next;
        }
    }
    public void delete(int no ) {
        HeroNode temp = head;
        while(true) {
            if (temp == null) {
                System.out.printf("没有找到编号%d的节点,不能删除\n",no);
                break;
            }
//            System.out.println("temp.next.no is " + temp.next.no);
            if (temp.next.no == no) {
                temp.next = temp.next.next;
                System.out.println("删除成功");
                break;
            }
            temp = temp.next;
        }
    }
    //显示链表
    public void list() {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //因为头节点不能动，需要辅助变量
        HeroNode temp = head.next;
        while (true) {
            //判断是否到链表最后
            if (temp == null ){
                break;
            }
            System.out.println(temp);
            //将next后移
            temp = temp.next;
        }
    }
}
//定义HeroNode,每个HeroNode对象都是一个节点
class HeroNode {
    public int no;
    public String name;
    public String nickname;
    public HeroNode next;   //指向下一个节点

    public HeroNode(int no, String name, String nickname) {
        this.no = no;
        this.name = name;
        this.nickname = nickname;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}